//2007.从双倍数组中还原原数组
//https://leetcode.cn/problems/find-original-array-from-doubled-array/?envType=daily-question&envId=2024-04-18
class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        sort(changed.begin(),changed.end());
        unordered_map<int,int> hash;
        for(int& n:changed) ++hash[n];

        vector<int> ret;
        for(int& n:changed)
        {
            if(hash[n] == 0) continue;
            --hash[n];
            if(hash.count(2*n) == 0 || (hash.count(2*n)&&hash[2*n]==0)) return {};
            --hash[2*n];
            ret.push_back(n);
        }
        return ret;
    }
};